#include "util.h"
//double seektime,writetime;
char *errmsg[]={
    "sucess",
    "invalid arguments",
};
/*
char* dbperror(struct hdb *db)
{
    static char *unknown_error="unknow error";
    if(db->error<sizeof(errmsg)/sizeof(char*))
        return errmsg[db->error];
	else return unknown_error;
}
*/
uint32 hash_fun(uchar *key,int len){
	uchar *it;
	uint32 h;
#define PRIME1		37
	for (it= key, h = 0; len--;)
		h = h * PRIME1 ^ (*it++ - ' ');
	return h;
}
char *abspath(char *fname)
{
    char *path=malloc(PATH_MAX);
	int len=0;
    if(realpath(fname,path)==NULL){
	    if(errno!=ENOENT){
		    fprintf(stderr,"get real path fail:%s\n",strerror(errno));
		    free(path);
		    return NULL;
		}
		if(realpath(".",path)!=NULL){
		    len=strlen(path);
			path[len]='/';
			len++;
			int cpylen=strlen(fname);
			cpylen=cpylen+len>PATH_MAX-1?PATH_MAX-len-1:cpylen;
			memcpy(path+len,fname,cpylen);
			len+=cpylen;
		}
	}
	else len=strlen(path);
	char *retpath=malloc(len+1);
	memcpy(retpath,path,len);
	retpath[len]='\0';
	free(path);
	return retpath;
}
int endwith(char *str,int ssiz,char *end,int esiz){
    if(esiz>ssiz) return false;
	return strncmp(str+ssiz-esiz,end,esiz)==0?true:false;
}
int mystrncmp(char *a,char *b,int len){
    int i,cmp=0;
	for(i=0;i<len&&cmp==0;i++)
	    cmp=*(a+i)-*(b+i);
	return cmp;
}
int seekwrite(int fd,char *buf,int32 len,uint64 offset){
    //struct timeval b,e;
	//gettimeofday(&b,NULL);
    if(lseek(fd,offset,SEEK_SET)<0){
	    printf("seek error:%s:pgno=%d fd=%d\n",strerror(errno),offset,fd);
		exit(1);
		return false;
	}
	//gettimeofday(&e,NULL);
	//seektime+=e.tv_sec-b.tv_sec+(e.tv_usec-b.tv_usec)/1000000.0;
	int wl=0,ret;
	while(wl<len){
	   if((ret=write(fd,buf+wl,len-wl))<=0){
	        printf("write error:%s\n",strerror(errno));
			exit(1);
			return false;
		}
	   wl+=ret;
	}
	//gettimeofday(&b,NULL);
	//writetime+=b.tv_sec-e.tv_sec+(b.tv_usec-e.tv_usec)/1000000.0;
	return wl;
}
int seekread(int fd,char *buf,int32 len,uint64 offset){
    if(lseek(fd,offset,SEEK_SET)<0){
	    printf("seek error:offset=%d\n",offset);
		exit(1);
		return false;
	}
	int rl=0,ret;
	while(rl<len){
	    if((ret=read(fd,buf+rl,len-rl))<=0){
		    printf("%s:read error:%s need read len=%d offset=%d\n",__func__,strerror(errno),len-rl,offset);
			exit(1);
			return false;
		}
		//struct stat st;
		//fstat(fd,&st);
		//printf("%s:file size=%d\n",__func__,st.st_size);
		rl+=ret;
	}
	return rl;
}
int lg2(int num){
    int power=1;
    while((num>>power)>0)
        power++;
	if(num==(1<<(power-1))) power--;
	return power;
}
uint32 prim(int num){
    static uint32 primnum[]={(1<<9)-1,(1<<10)-1,(1<<11)-1,(1<<12)-1,(1<<13)-1,(1<<14)-1,(1<<15)-1,(1<<16)-1,(1<<17)-1};
	int i=0;
	while(i<sizeof(primnum)/sizeof(uint32)&&primnum[i]<num) i++;
	return i>sizeof(primnum)/sizeof(uint32)?primnum[i-1]:primnum[i];
}
int readn(int fd,char *buf,int len){
    int num=0,ret;
	while(num<len){
	    if((ret=read(fd,buf+num,len-num))<0){
		    perror("read()");
			if(errno==EAGAIN)
			    continue;
			else
			    return num;
		}else if(ret==0)
		    return num;
		num+=ret;
	}
	return num;
}
int writen(int fd,char *buf,int len){
    int num=0,ret;
	while(num<len){
	    if((ret=write(fd,buf+num,len-num))<0)
		    if(errno==EAGAIN)
			     continue;
		    else
			    return num;
		else if(ret==0)
		    return num;
		num+=ret;
	}
	return num;
}
struct bstring* strnew(int siz){
    if(siz<=0) siz=DEF_STR_SIZ;
    struct bstring *str=malloc(sizeof(struct bstring));
	str->max=siz;
	str->siz=0;
	str->array=malloc(siz);
	return str;
}
struct bstring *strcreate(char *array,int len){
    struct bstring *str=malloc(sizeof(struct bstring));
	if(str==NULL) return NULL;
	str->max=str->siz=len;
	if((str->array=malloc(len))==NULL){
	    free(str);
		return NULL;
	}
	memcpy(str->array,array,len);
	return str;
}
int strassign(struct bstring *str,char *cs,int siz){
    if(str->max<siz){
	    str->max=siz;
	    str->array=realloc(str->array,str->max);
	}
	memcpy(str->array,cs,siz);
	return true;
}
int strcompare(struct bstring *str,char *peer,int siz){
    int cmpsiz=siz>str->siz?str->siz:siz;
	int cmp=strncmp(str->array,peer,cmpsiz);
	if(cmp==0) cmp=str->siz-siz;
	return cmp;
}
int strcomparestr(struct bstring *str,struct bstring *ref){
    if(str==NULL||ref==NULL) return 0;
    int cmpsiz=ref->siz>str->siz?str->siz:ref->siz;
	int cmp=strncmp(str->array,ref->array,cmpsiz);
	if(cmp==0) cmp=str->siz-ref->siz;
	return cmp;
}
void strdel(struct bstring *str){
    if(str->array!=NULL) free(str->array);
    free(str);
}
int stradjust(struct bstring *str,int siz){
    if(str->max<siz){
	    str->max=siz;
	    str->array=realloc(str->array,str->max);
	}
	str->siz=siz;
	return true;
}
int stradd(struct bstring *str,char *cs,int siz){
    if(str->max-str->siz>=siz){
	    memcpy((char*)str->array+str->siz,cs,siz);
		str->siz+=siz;
	}else{
		while(str->max<str->siz+siz) str->max<<=1;
		printf("%s:max=%d\n",__func__,str->max);
		str->array=realloc(str->array,str->max);
		memcpy(str->array+str->siz,cs,siz);
		str->siz+=siz;
	}
	return true;
}
int bstrdup(struct bstring *tstr,struct bstring *sstr){
    if(tstr->max<sstr->siz){
		tstr->array=realloc(tstr->array,sstr->siz);
		tstr->max=sstr->siz;
	}
	memcpy(tstr->array,sstr->array,sstr->siz);
	tstr->siz=sstr->siz;
	return true;
}

#define SWAP(x,y)\
    do{\
	    (x)=(x)^(y);\
		(y)=(y)^(x);\
		(x)=(x)^(y);\
	}while(false)
void sort64(uint64 a[],int len){
    int i,j,k,p;
	if(len<=1) return;
	i=len>>1;
	while(i>0){
	    j=i;
		k=len>>1;
		while(j<=k){
		    p=j;
			j<<=1;
		    if(j<len&&a[j-1]<a[j]) j++;
			if(a[p-1]>a[j-1]) break;
			SWAP(a[j-1],a[p-1]);
		}
		i--;
	}
	i=len;
	while(i>1){
	    i--;
	    SWAP(a[0],a[i]);
		j=1;
		k=i>>1;
		while(j<=k){
		    p=j;
			j<<=1;
			if(j<i&&a[j-1]<a[j]) j++;
			if(a[j-1]>a[p-1]) SWAP(a[p-1],a[j-1]);
			else break;
		}
	}
}
struct strlist* listcreate(int num){
    if(num<=0) num=DEF_LIST_NUM;
	struct strlist *list=malloc(sizeof(struct strlist));
	list->max=num;
	list->siz=0;
	list->str_array=malloc(sizeof(struct bstring*)*list->max);
	return list;
}
int listadd(struct strlist *list,struct bstring *str){
    if(list->str_array==NULL){
	    list->str_array=malloc(sizeof(struct bstring*)*DEF_LIST_NUM);
		list->max=DEF_LIST_NUM;
		list->siz=0;
	}
	if(list->siz>=list->max){
	    list->max<<=1;
	    list->str_array=realloc(list->str_array,list->max);
	}
	list->str_array[list->siz++]=str;
	return list->siz;
}
struct bstring* listget(struct strlist *list,int i){
    if(i<0||i>=list->siz) return NULL;
	return list->str_array[i];
}
int listerase(struct strlist *list,int i){
    if(i<0||i>=list->siz) return false;
	strdel(list->str_array[i]);
	memmove(list->str_array+i,list->str_array+i+1,sizeof(struct bstring*)*(list->siz-i-1));
	list->siz--;
	return list->siz;
}
void listdel(struct strlist *list){
    int i;
	for(i=0;i<list->siz;i++) strdel(list->str_array[i]);
	free(list->str_array);
	free(list);
}
int xatoi(char *key,int len){
    int i=0;
	while(i<len&&key[i]=='0') i++;
	int k=0;
	while(i<len){
	    k=k*10+key[i]-'0';
		i++;
	}
	return k;
}
#define DEF_HA_BUCKETS 5
struct harray* hashcreate(int nb){
    if(nb<=0) nb=DEF_HA_BUCKETS;
	struct harray *ha=malloc(sizeof(struct harray));
	if(ha==NULL){
	    printf("Mem alloc\n");
		return NULL;
	}
	ha->nbucket=nb;
	ha->first=NULL;
	ha->last=NULL;
	ha->buckets=calloc(ha->nbucket,sizeof(struct item*));
	if(ha->buckets==NULL){
	    printf("Mem allc\n");
		free(ha);
		return NULL;
	}
	ha->nrec=0;
	return ha;
}
int hashput(struct harray *ha,char *key,int ksiz,void *val){
    uint32 hv1=hash_fun((uchar*)key,ksiz);
	uint16 hv2=hv1&0xff;
	hv1=hv1%ha->nbucket;
	struct item *it=ha->buckets[hv1];
	struct item *pi=it;
	int cmp,cmpsiz;
	while(it!=NULL){
	    if(it->hash==hv2){
		    cmpsiz=it->key->siz>ksiz?ksiz:it->key->siz;
		    cmp=strncmp(key,it->key->array,cmpsiz);
			if(cmp==0) cmp=ksiz-it->key->siz;
			if(cmp==0){
			    //strassign(it->key,key,ksiz);
				//return 2;
				return false;
			}else if(cmp<0){
			    pi=it;
				it=it->left;
			}else{
			    pi=it;
				it=it->right;
			}
		}else if(hv2<it->hash){
		    pi=it;
			it=it->left;
		}else{
		    pi=it;
			it=it->right;
		}
	}
	it=malloc(sizeof(struct item));
	it->key=strcreate(key,ksiz);
	it->val=val;
	it->hash=hv2;
	it->left=it->right=NULL;
	if(pi==NULL){
	    ha->buckets[hv1]=it;
	}else{
	    if(hv2<pi->hash||(hv2==pi->hash&&cmp>0)) pi->left=it;
		else pi->right=it;
	}
	if(ha->last!=NULL)
	    ha->last->next=it;
	it->pre=ha->last;
	it->next=NULL;
	ha->last=it;
	if(ha->first==NULL) ha->first=it;
	ha->nrec++;
	return true;
}
int hashputkeep(struct harray *ha,struct bstring* key,void *val){
    uint32 hv1=hash_fun((uchar*)key->array,key->siz);
	uint16 hv2=hv1&0xff;
	hv1=hv1%ha->nbucket;
	struct item *it=ha->buckets[hv1];
	struct item *pi=it;
	int cmp;
	while(it!=NULL){
	    if(it->hash==hv2){
		    cmp=strcomparestr(key,it->key);
			if(cmp==0){
				return false;
			}else if(cmp<0){
			    pi=it;
				it=it->left;
			}else{
			    pi=it;
				it=it->right;
			}
		}else if(hv2<it->hash){
		    pi=it;
			it=it->left;
		}else{
		    pi=it;
			it=it->right;
		}
	}
	it=malloc(sizeof(struct item));
	it->key=key;
	it->val=val;
	it->hash=hv2;
	it->left=it->right=NULL;
	if(pi==NULL){
	    ha->buckets[hv1]=it;
	}else{
	    if(hv2<pi->hash||(hv2==pi->hash&&cmp>0)) pi->left=it;
		else pi->right=it;
	}
	if(ha->last!=NULL)
	    ha->last->next=it;
	it->pre=ha->last;
	it->next=NULL;
	ha->last=it;
	if(ha->first==NULL) ha->first=it;
	ha->nrec++;
	return true;
}
int recput(struct harray *ha,char *key,char *val){
    struct bstring *k=strcreate(key,strlen(key));
	struct bstring *v=strcreate(val,strlen(val));
	return hashputkeep(ha,k,v);
}
int hashputrep(struct harray *ha,char *key,int ksiz,void *val){
    uint32 hv1=hash_fun((uchar*)key,ksiz);
	uint16 hv2=hv1&0xff;
	hv1=hv1%ha->nbucket;
	struct item *it=ha->buckets[hv1];
	struct item *pi=it;
	int cmp,cmpsiz;
	while(it!=NULL){
	    if(it->hash==hv2){
		    cmpsiz=it->key->siz>ksiz?ksiz:it->key->siz;
		    cmp=strncmp(key,it->key->array,cmpsiz);
			if(cmp==0) cmp=ksiz-it->key->siz;
			if(cmp==0){
			    //strassign(it->key,key,ksiz);
				it->val=val;
				return true;
			}else if(cmp<0){
			    pi=it;
				it=it->left;
			}else{
			    pi=it;
				it=it->right;
			}
		}else if(hv2<it->hash){
		    pi=it;
			it=it->left;
		}else{
		    pi=it;
			it=it->right;
		}
	}
	it=malloc(sizeof(struct item));
	it->key=strnew(ksiz);
	memcpy(it->key->array,key,ksiz);
	//it->val=strnew(vsiz);
	//memcpy(it->val->array,val,vsiz);
	it->val=val;
	it->hash=hv2;
	it->left=it->right=NULL;
	if(pi==NULL){
	    ha->buckets[hv1]=it;
	}else{
	    if(hv2<pi->hash||(hv2==pi->hash&&strcompare(pi->key,key,ksiz)>0)) pi->left=it;
		else pi->right=it;
	}
	if(ha->last!=NULL)
	    ha->last->next=it;
	it->pre=ha->last;
	it->next=NULL;
	ha->last=it;
	if(ha->first==NULL) ha->first=it;
	ha->nrec++;
	return true;
}
int hashputstr(struct harray *ha,struct bstring *key,struct bstring *val){
    uint32 hv1=hash_fun((uchar*)key->array,key->siz);
	uint16 hv2=hv1&0xff;
	hv1=hv1%ha->nbucket;
	struct item *it=ha->buckets[hv1];
	struct item *pi=it;
	int cmp;
	while(it!=NULL){
	    if(it->hash==hv2){
		    cmp=strcomparestr(it->key,key);
			if(cmp==0){
			    //strassign(it->key,key,ksiz);
				//return 2;
				return false;
			}else if(cmp<0){
			    pi=it;
				it=it->left;
			}else{
			    pi=it;
				it=it->right;
			}
		}else if(hv2<it->hash){
		    pi=it;
			it=it->left;
		}else{
		    pi=it;
			it=it->right;
		}
	}
	it=malloc(sizeof(struct item));
	it->key=key;
	it->val=val;
	it->hash=hv2;
	it->left=it->right=NULL;
	if(pi==NULL){
	    ha->buckets[hv1]=it;
	}else{
	    if(hv2<pi->hash||(hv2==pi->hash&&cmp>0)) pi->left=it;
		else pi->right=it;
	}
	if(ha->last!=NULL)
	    ha->last->next=it;
	it->pre=ha->last;
	it->next=NULL;
	ha->last=it;
	if(ha->first==NULL) ha->first=it;
	ha->nrec++;
	return true;
}
int hashexsit(struct harray *ha,char *key,int ksiz){
    uint32 hv1=hash_fun((uchar*)key,ksiz);
	uint16 hv2=hv1&0xff;
	int cmp;
	hv1=hv1%ha->nbucket;
	struct item* it=ha->buckets[hv1];
	while(it!=NULL){
	    if(it->hash==hv2){
		    cmp=strcompare(it->key,key,ksiz);
			if(cmp==0){
			    return true;
			}else if(cmp>0)
			    it=it->left;
			else it=it->right;
		}else if(it->hash>hv2) it=it->left;
		else it=it->right;
	}
	return false;
}
struct bstring* hashgetstr(struct harray *ha,struct bstring *key){
    uint32 hv1=hash_fun((uchar*)key->array,key->siz);
	uint16 hv2=hv1&0xff;
	int cmp;
	hv1=hv1%ha->nbucket;
	struct item* it=ha->buckets[hv1];
	while(it!=NULL){
	    if(it->hash==hv2){
		    cmp=strcompare(it->key,key->array,key->siz);
			if(cmp==0){
			    return it->val;
			}else if(cmp>0)
			    it=it->left;
			else it=it->right;
		}else if(it->hash>hv2) it=it->left;
		else it=it->right;
	}
	return NULL;
}
void* hashget(struct harray *ha,char *key,int ksiz){
    uint32 hv1=hash_fun((uchar*)key,ksiz);
	uint16 hv2=hv1&0xff;
	int cmp;
	hv1=hv1%ha->nbucket;
	struct item* it=ha->buckets[hv1];
	while(it!=NULL){
	    if(it->hash==hv2){
		    cmp=strcompare(it->key,key,ksiz);
			if(cmp==0){
			    //*vsiz=it->val->siz;
			    return it->val;
			}else if(cmp>0)
			    it=it->left;
			else it=it->right;
		}else if(it->hash>hv2) it=it->left;
		else it=it->right;
	}
	return NULL;
}
void* hasherase(struct harray *ha,char *key,int ksiz){
    uint32 hv1=hash_fun((uchar*)key,ksiz);
	uint16 hv2=hv1&0xff;
	int cmp;
	hv1=hv1%ha->nbucket;
	struct item* it=ha->buckets[hv1];
	struct item *pi=it;
	while(it!=NULL){
	    if(it->hash==hv2){
		    if((cmp=strcompare(it->key,key,ksiz))==0)
			    break;
			else if(cmp<0){
			   pi=it;
			   it=it->right;
			}else{
			   pi=it;
			   it=it->left;
			}
		}else if(it->hash>hv2){
		    pi=it;
			it=it->left;
		}else{
		    pi=it;
			it=it->right;
		}
	}
	if(it==NULL){
	    printf("%s:error!locate\n",__func__);
		exit(1);
	}
	if(it->left==NULL){
	    if(pi==it) ha->buckets[hv1]=it->right;
		else if(pi->left==it) pi->left=it->right;
		else pi->right=it->right;
	}else if(it->right==NULL){
	    if(pi==it) ha->buckets[hv1]=it->left;
		else if(pi->left==it) pi->left=it->left;
		else pi->right=it->left;
	}else{
	    struct item *ti=it->left;
		struct item *pti=ti;
		while(ti->right!=NULL){
		    pti=ti;
			ti=ti->right;
		}
		if(pi==it) ha->buckets[hv1]=ti;
		else if(pi->left==it) pi->left=ti;
		else pi->right=ti;
		if(ti!=pti){
		    pti->right=ti->left;
		    ti->left=it->left;
		}
		ti->right=it->right;
	}
	if(it->pre!=NULL) it->pre->next=it->next;
	else ha->first=it->next;
	if(it->next!=NULL) it->next->pre=it->pre;
	else ha->last=it->pre;
	strdel(it->key);
	void *val=it->val;
	free(it);
	ha->nrec--;
	return val;
	//return true;
}
int hasherasestr(struct harray *ha,char *key,int ksiz){
    uint32 hv1=hash_fun((uchar*)key,ksiz);
	uint16 hv2=hv1&0xff;
	int cmp;
	hv1=hv1%ha->nbucket;
	struct item* it=ha->buckets[hv1];
	struct item *pi=it;
	while(it!=NULL){
	    if(it->hash==hv2){
		    if((cmp=strcompare(it->key,key,ksiz))==0)
			    break;
			else if(cmp<0){
			   pi=it;
			   it=it->right;
			}else{
			   pi=it;
			   it=it->left;
			}
		}else if(it->hash>hv2){
		    pi=it;
			it=it->left;
		}else{
		    pi=it;
			it=it->right;
		}
	}
	if(it==NULL){
	    printf("%s:error!locate\n",__func__);
		exit(1);
		return false;
	}
	if(it->left==NULL){
	    if(pi==it) ha->buckets[hv1]=it->right;
		else if(pi->left==it) pi->left=it->right;
		else pi->right=it->right;
	}else if(it->right==NULL){
	    if(pi==it) ha->buckets[hv1]=it->left;
		else if(pi->left==it) pi->left=it->left;
		else pi->right=it->left;
	}else{
	    struct item *ti=it->left;
		struct item *pti=ti;
		while(ti->right!=NULL){
		    pti=ti;
			ti=ti->right;
		}
		if(pi==it) ha->buckets[hv1]=ti;
		else if(pi->left==it) pi->left=ti;
		else pi->right=ti;
		if(ti!=pti){
		    pti->right=ti->left;
		    ti->left=it->left;
		}
		ti->right=it->right;
	}
	if(it->pre!=NULL) it->pre->next=it->next;
	else ha->first=it->next;
	if(it->next!=NULL) it->next->pre=it->pre;
	else ha->last=it->pre;
	strdel(it->key);
	strdel(it->val);
	free(it);
	ha->nrec--;
	return true;
}
void hashdel(struct harray *ha,void(*del)(void*)){
    struct item *it=ha->first;
	struct item *temp;
	while(it!=NULL){
	    temp=it->next;
		if(it->key!=NULL) strdel(it->key);
		if(del!=NULL) del(it->val);
		free(it);
		it=temp;
	}
	free(ha->buckets);
	free(ha);
}
void hashdelstr(struct harray *ha){
    struct item *it=ha->first;
	struct item *temp;
	while(it!=NULL){
	    temp=it->next;
		strdel(it->key);
		strdel(it->val);
		free(it);
		it=temp;
	}
	free(ha->buckets);
	free(ha);
}
struct bstring** hashtoarray(struct harray *ha,int *n){
	if(ha->nrec==0) return NULL;
    struct bstring **array=malloc((ha->nrec<<1)*sizeof(struct bstring*));
	struct item **stack=malloc(ha->nrec*sizeof(struct item*));
	int beg,end,i;
	*n=0;
	for(i=0;i<ha->nbucket;i++){
	    if(ha->buckets[i]!=NULL){
	        stack[0]=ha->buckets[i];
			beg=0;
			end=1;
			while(beg<end){
			    array[*n++]=stack[beg]->key;
				array[*n++]=stack[beg]->val;
			    if(stack[beg]->left!=NULL) stack[end++]=stack[beg]->left;
				if(stack[beg]->right!=NULL) stack[end++]=stack[beg]->right;
				beg++;
			}
		}
	}
	free(stack);
	return array;
}
void hashand(struct harray *ha,struct harray *hb){
    struct item *it=ha->first;
	struct item *tmp;
	while(it!=NULL){
	    tmp=it->next;
	    if(!hashexsit(hb,it->key->array,it->key->siz)){
		    hasherase(ha,it->key->array,it->key->siz);
		}
		it=tmp;
	}
}
void hashor(struct harray *ha,struct harray *hb){
    struct item *it=hb->first;
	while(it!=NULL){
	    hashput(ha,it->key->array,it->key->siz,it->val);
	}
}
struct harray *strtohash(char *str,int siz){
    struct harray *ha=hashcreate(0);
	char *ptr=str;
	int vsiz,ksiz;
	struct bstring *key,*val;
	while(ptr<str+siz){
	    ksiz=*((int32*)ptr);
	    ptr+=sizeof(int32);
		printf("%s:ksiz=%d\n",__func__,ksiz);
		key=strcreate(ptr,ksiz);
		ptr+=ksiz;
		vsiz=*((int32*)ptr);
		printf("%s:vsiz=%d\n",__func__,vsiz);
		ptr+=sizeof(int32);
		val=strcreate(ptr,vsiz);
		ptr+=vsiz;
		if(!hashputstr(ha,key,val)) printf("%s:put to hash fail\n",__func__);
	}
	return ha;
}
struct item* hashremove(struct harray *ha,char *key,int ksiz){
    uint32 hv1=hash_fun((uchar*)key,ksiz);
	uint16 hv2=hv1&0xff;
	int cmp;
	hv1=hv1%ha->nbucket;
	struct item* it=ha->buckets[hv1];
	struct item *pi=it;
	while(it!=NULL){
	    if(it->hash==hv2){
		    if((cmp=strcompare(it->key,key,ksiz))==0)
			    break;
			else if(cmp<0){
			   pi=it;
			   it=it->right;
			}else{
			   pi=it;
			   it=it->left;
			}
		}else if(it->hash>hv2){
		    pi=it;
			it=it->left;
		}else{
		    pi=it;
			it=it->right;
		}
	}
	if(it==NULL){
	    printf("%s:error!locate\n",__func__);
		exit(1);
		return NULL;
	}
	if(it->left==NULL){
	    if(pi==it) ha->buckets[hv1]=it->right;
		else if(pi->left==it) pi->left=it->right;
		else pi->right=it->right;
	}else if(it->right==NULL){
	    if(pi==it) ha->buckets[hv1]=it->left;
		else if(pi->left==it) pi->left=it->left;
		else pi->right=it->left;
	}else{
	    struct item *ti=it->left;
		struct item *pti=ti;
		while(ti->right!=NULL){
		    pti=ti;
			ti=ti->right;
		}
		if(pi==it) ha->buckets[hv1]=ti;
		else if(pi->left==it) pi->left=ti;
		else pi->right=ti;
		if(ti!=pti){
		    pti->right=ti->left;
		    ti->left=it->left;
		}
		ti->right=it->right;
	}
	return it;
}
int hashtraverse(struct harray* ha){
    struct item *stack[100];
	int tail,head;
	int i;
	printf("%s:%d rec\n",__func__,ha->nrec);
	for(i=0;i<ha->nbucket;i++){
	    if(ha->buckets[i]==NULL){
	        printf("%s:%d no child\n",__func__,i);
		    continue;
 	    }else printf("%s:bucket %d:\n",__func__,i);
	    stack[0]=ha->buckets[i];
		tail=0;head=1;
	    while(tail!=head){
	        struct item *it=stack[tail++];
	        printf("%s:key=%d\n",__func__,*((uint64*)it->key->array));
		    if(it->right!=NULL) stack[head++]=it->right;
		    if(it->left!=NULL) stack[head++]=it->left;
		    if(head>=100)exit(1);
		}
	}
	struct item *it=ha->first;
	printf("%s:link seq:\n",__func__);
	while(it!=NULL){
	    printf("%s:key=%d\n",__func__,*((uint64*)it->key->array));
		it=it->next;
	}
	return true;
}
void hashheadout(struct harray *ha,int n,void(*delfun)(void *)){
    struct item *it=ha->first;
	//hashtraverse(ha);
	if(ha->nrec<n) n=ha->nrec;
	ha->nrec-=n;
	while(n>0&&it!=NULL){
	    DEBUG(printf("%s:del key=%d ksiz=%d\n",__func__,*((uint64*)(it->key->array)),it->key->siz));
		struct item *tmp=it->next;
		hashremove(ha,it->key->array,it->key->siz);
		delfun(it->val);
		strdel(it->key);
		free(it);
		it=tmp;
		n--;
	}
	ha->first=it;
	if(it!=NULL) it->pre=NULL;
}
void hashtailout(struct harray *ha,int n,void(*delfun)(void*)){
    struct item *it=ha->last;
	if(n>ha->nrec) n=ha->nrec;
	ha->nrec-=n;
	DEBUG(printf("%s:remove from tail %d rec\n",__func__,n));
	
	while(n>0&&it!=NULL){
	    DEBUG(printf("%s:del key=%d\n",__func__,*((uint64*)it->key->array)));
	    hashremove(ha,it->key->array,it->key->siz);
	    delfun(it->val);
		strdel(it->key);
		struct item *tmp=it->pre;
		free(it);
		it=tmp;
		n--;
	}
	ha->last=it;
	if(it!=NULL) it->next=NULL;
}
void* hashfirst(struct harray *ha,struct bstring **key){
    if(ha==NULL||ha->nrec==0) return NULL;
	ha->iter=ha->first;
	if(key!=NULL) *key=ha->iter->key;
	return ha->iter->val;
}
void *hashlast(struct harray *ha,struct bstring **key){
    if(ha==NULL||ha->nrec==0)return NULL;
	ha->iter=ha->last;
	if(key!=NULL) *key=ha->iter->key;
	return ha->iter->val;
}
void* hashnext(struct harray *ha,struct bstring **key){
    if(ha->iter==NULL||ha->iter==ha->last) return NULL;
	ha->iter=ha->iter->next;
	if(ha->iter==NULL) return NULL;
	if(key!=NULL) *key=ha->iter->key;
	return ha->iter->val;
}
void *hashpre(struct harray *ha,struct bstring **key){
    if(ha->iter==NULL||ha->iter==ha->first) return NULL;
	ha->iter=ha->iter->pre;
	if(ha->iter==NULL) return NULL;
	if(key!=NULL) *key=ha->iter->key;
	return ha->iter->val;
}
struct hashcache* hashcachecreate(int nb,int maxbytes,int initsiz,double incratio){
    struct hashcache *hc=malloc(sizeof(struct hashcache));
	if(hc==NULL) return NULL;
	if(nb<3) nb=3;
	if(maxbytes<1024) maxbytes=1024;
	if((hc->buckets=calloc(nb,sizeof(struct item*)))==NULL){
	    free(hc);
		return NULL;
	}
	hc->first=hc->last=hc->ffirst=hc->flast=NULL;
	hc->curbytes=hc->nrec=0;
	hc->nbucket=nb;
	hc->initsiz=initsiz<=0?4:initsiz;
	hc->incratio=(incratio>0.0&&incratio<=2.0)?incratio:1.2;
	hc->maxbytes=maxbytes;
	return hc;
}
int hashcacheput(struct hashcache *hc,char *key,int ksiz,void *val){
   //..
   return 0;
}/*
int defcmp(char *k1,int s1,char *k2,int s2){
    int cmpsiz=s1>s2?s2:s1;
	return strncmp(k1,k2,cmpsiz);
}
struct twoidxtree* tinew(int(cmp1*)(char *,int,char*,int),int(cmp2)(char*),int,char*,int){
    struct twoidxtree *root=malloc(sizeof(struct twoidxtree));
	root->root=NULL;
	if(cmp1==NULL) root->cmp1=defcmp;
	else root->cmp1=cmp1;
	if(cmp2==NULL) root->cmp2=defcmp;
	else root->cmp2=cmp2;
	return root;
}
int tiput(struct twoidxtree *tree,char *k1,int s1,char *k2,int s2){
    
}*/
